package com.example.lettcode._202411._20241115;

/*
303. 区域和检索 - 数组不可变

简单
给定一个整数数组  nums，处理以下类型的多个查询:
计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right
实现 NumArray 类：
NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] )


示例 1：
输入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]
 */
public class _01_qu_yu_he_jian_suo {
    public static void main(String[] args) {
        int[] nums = {-2, 0, 3, -5, 2, -1};
        NumArray numArray = new NumArray(nums);
        System.out.println(numArray.sumRange(0, 2));
        System.out.println(numArray.sumRange(2, 5));
        System.out.println(numArray.sumRange(0, 5));
    }

}

class NumArray {
    private int[] ints;

    /*
        这种方式可以达成效果，但是执行耗时和消耗内存都比较大，因为每次sumRange就需要遍历一次数组
        可以在初始化的时候，就将nums中的结果进行统计，后续就不需要进行遍历了，只需要在初始化中进行一次遍历即可。
        public NumArray(int[] nums) {
            this.nums = nums;
        }

        public int sumRange(int left, int right) {
            int sum = 0;
            while (left <= right) {
                sum += nums[left];
                left++;
            }
            return sum;
        }
     */

    /*
        这种方式，在初始化时，就进行了累加的计算了，保证sumRange的计算是O(1)
        public NumArray(int[] nums) {
            ints = new int[nums.length];

            ints[0] = nums[0];
            for (int i = 1; i < nums.length; i++) {
                ints[i] = ints[i-1] + nums[i];
            }
        }

        public int sumRange(int left, int right) {
            return left == 0 ? ints[right] : ints[right] - ints[left-1];
        }
     */

    /*
        下面的方式，初始化数组时，使数组长度+1，就不需要考虑left = 0的情况了，使的代码更加的简洁
     */
    public NumArray(int[] nums) {
        int n = nums.length;
        ints = new int[n+1];

        for (int i = 0; i < nums.length; i++) {
            ints[i+1] = ints[i] + nums[i];
        }
    }

    public int sumRange(int left, int right) {
        return ints[right+1] - ints[left];
    }
}
